#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int merge(vector<int>& nums, int l, int r, int m) {
        int res = 0,i=0;
        int p1 = l,p2 = m+1;
        vector<int> help(r - l + 1);
        while (p1 <= m && p2 <= r) {
            if (nums[p1] <= nums[p2]) {
                help[i++] = nums[p1++];
            }
            else {
                res += m - p1 + 1;
                help[i++] = nums[p2++];
            }
        }
        while (p1 <= m) {
            help[i++] = nums[p1++];
        }
        while (p2 <= r) 
            help[i++] = nums[p2++];
        for (i = 0; i < help.size() ; i++)
            nums[l + i] = help[i];
        return res;
    }
    int process(vector<int>& nums, int l, int r) {
        if (l == r) {
            return 0;
        }
        int m = l + ((r - l) >> 1);
        return process(nums, l, m) + process(nums, m + 1, r) 
            + merge(nums, l, r, m);

    }
    int reversePairs(vector<int>& record) {
        if (record.size() == 0)
            return 0;
        return process(record, 0, record.size() - 1);

    }
};